import collections
class Solution(object):
    def restoreArray(self, adjacentPairs):
        n = len(adjacentPairs) + 1
        ans = [0] * n
        d = collections.defaultdict(set)
        for u, v in adjacentPairs:
            d[u].add(v)
            d[v].add(u)
        for num in d:
            if len(d[num]) == 1:
                start = num
                break
        ans[0] = start
        for i in range(1, n):
            ans[i] = d[ans[i - 1]].pop()
            if i < n - 1:
                d[ans[i]].remove(ans[i - 1])
        return ans